Counting

CSE 16: Applied Discrete Mathematics

Instructor: Owen Arden

Winter 2023

Counting? Seriously?

… this joke is getting old, isn’t it?

Counting ends up being an important topic in discrete math, and is often not as simple as it seems.

How many squads?

There are 74 distinct characters in the base Super Smash Bros. Ultimate (if you count the Pokemon Trainer as one character). How many different 5 vs 5 tag team matches are there?

IMPORTANT: Players can’t choose the same character twice.

3.736688797550822e18!!!

Counting sequences from sets

Scenario:

The breakfast special includes a drink (Coffee or OJ), a main course (pancakes or eggs), and a side (bacon, sausage, hash browns).

How many different breakfasts selections are there?

Product rule: Let \(A_1, A_2, ..., A_n\) be finite sets. The number of sequences \(|[a_1, a_2, ..., a_n]|\), where \(a_i \in A_i\), is the cardinality of the cartesian product of the sets: \[|A_1 \times A_2 \times ... \times A_n| = |A_1| * |A_2| * ... * |A_n|\]

So \(|\{\text{coffee, oj}\}|*|\{\text{pancake, eggs}\}|*|\{\text{bacon, sausage, eggs}\}| = 12\)

So how many squads?

Are there \(|74|^{10}\) 5 vs 5 matches then?

\[|74|^{10}=4.923990397355877e18\]

hmm… what is different?

Important note

The product rule is used for independent choices.
- For example, choosing OJ for breakfast didn’t affect which choices were available for mains or sides.
- Choosing Smash characters is not independent: each player’s choice reduces the characters available for the next choice.
Suppose I told you that each player has \(P_5 = 1933051680\) choices of team lineups.
- The choices each player makes are independent of each other. (We can both choose Pikachu)
- So \(P_5 * P_5 = 3.736688797550822e18\) gives us the number.

The sum rule

For the number of breakfast selections and the number of matches (given \(P_5\)), we chose one element from each set.
- For example \(\text{coffee},\text{eggs},\text{bacon}\), or one lineup from Player 1’s \(P_5\) choices and one from Player 2’s \(P_5\) choices.
What about when only one selection is made from multiple sets? For this, we use the sum rule.

Sum rule: Consider \(n\) sets \(A_1, A_2, ..., A_n\). If the sets are pairwise disjoint (\(A_i \cap A_j = \emptyset\) for \(i \neq j\)), then \[|A_1 \cup A_2 \cup ... \cup A_n| = |A_1| + |A_2| + ... + |A_n|\]

Example: all matches

What if we wanted to know the number of all tag team matches (both 3 vs 3 and 5 vs 5)?

If \(P_3\) is the number of choices each player has for 3-character lineups, then the number possible matches is: \[ P_3 * P_3 + P_5 * P_5 \]

In other words, the number of 3 vs 3 plus the number of 5 vs 5.

Note we are combining the product rule and the sum rule together here:
- One perspective: we are choosing either a pair of 3-character lineups or a pair of 5-character lineups.
- \(P_3*P_3\) is the number of 3-character pairs, and \(P_5*P_5\) is the number of 5-character pairs.

Bijection rule

Bijection rule: Let \(S\) and \(T\) be two finite sets. If there is a bijection from \(S\) to \(T\), then \(|S|=|T|\).

This is useful if we know how to count one set and can map every element to another set which might be harder to count.

Example: Counting tickets to know how many people are in a theater.
- Let \(T\) be the set of tickets and \(P\) be the set of people. If the usher enforced a 1-to-1 correspondence (a bijection) between tickets and people entering the theater, then \(|T|=|P|\).

k-to-1 rule

We can use other mappings to count sets in terms of other sets.

k-to-1 correspondence: Let \(X\) and \(Y\) be finite sets. The function \(f:X \to Y\) is a k-to-1 correspondence if for every \(y \in Y\), there are exactly \(k\) different \(x \in X\) such that \(f(x)=y\).

k-to-1 rule: Suppose there is a k-to-1 correspondence from a finite set \(A\) to a finite set \(B\). Then \(|B|=|A|/k\).

Example: A bounce house operator needs to make sure no more than 10 kids are in the bounce house at a time.

Let \(K\) be the set of kids.
Each kid has to take off their shoes before entering (and put them back on when leaving).
Let \(S\) be the set of shoes.
Since there is a 2-to-1 correspondence between the number of shoes and the kids inside, \(|K|= |S|/2\).

Generalized product rule

But seriously, how do we count the number of 5 vs 5 lineups?

We couldn’t use the product rule to calculate \(P_5\) since the choices were not independent, but we can use a generalization of the product rule as long as the number of choices at each step doesn’t depend on previous choices.

Generalized product rule

Consider a set \(S\) of sequences of \(k\) items. Suppose there are:

\(n_1\) choices for the first item

for every possible choice of the first item, there are \(n_2\) choices for the second item.

for every possible choice of the first two items, there are \(n_3\) choices for the third item.

…

for every possible choice of the first \(k-1\) items, there are \(n_k\) choices for the \(k^{\text{th}}\) item. :

Then \(|S| = n_1 * n_2 * ... * n_k\).

Choosing a sequence of 5 characters

Are we there yet?

There are 74 characters (if you count the Pokemon trainer as one), So there are 74 choices for the first character, 73 for the second, and so on.

Does the number of choices depend on which characters were previously chosen?

No! And \(P_5 = 74*73*72*71*70 = 1933051680\)

Permutations

Counting \(P_5\) is an example of a common application of the generalized product rule: for counting permutations.

r-permutation: An r-permutation is a sequence of \(r\) items all taken from the same set.

Example: Pikachu, Kirby, Link is a 3-permutation of the set of Smash characters.

P(n,r): the number of r-permutations from a set of size n.: Let \(r\) and \(n\) be positive integers with \(r \leq n\). The number of r-permutations from a set with \(n\) elements is: \(P(n,r) = \dfrac{n!}{(n-r)!}\)

Example: \[P_5 = P(74,5) = \dfrac{74!}{(74-5)!} = 74*73*72*71*70\]

Example: PIN code constraints

A bank PIN is a string of four digits, each digit 0-9. How many choices are there for a PIN if the last digit must be odd and all the digits must be different from each other?

Tricky! Strategy: count the digit with extra contraints separately.

How many ways to choose an odd digit in 0-9? 10/2 = 5.

That takes care of the last digit, but also reduces the available digits by 1.

For the remaining 3 digits, one is a choice from the 9 remaining digits, one is a choice from 8 digits (since two other digits have been chosen), and one is a choice from 7 digits.

We now have the 4 sets we need to choose our sequence from. Using the product rule, the number of possible PIN codes is \[9 \cdot 8 \cdot 7 \cdot 5\].

Subsets (combinations)

What if the order of the characters didn’t matter? Say we wanted to count the number of distinct 3-character teams.

In this case the sequences (Pikachu, Kirby, Link), (Kirby, Pikachu, Link) etc are counted only once.
The teams are now more like sets than sequences.

r-subset: An r-subset or r-combination is a subset of \(r\) items all taken from the same set.

Counting r-subsets

We already have an easy way to count r-permutations, but this would overcount r-subsets.
But! It turns out it overcounts by the same ratio for each subset.
Consider the number of permutations of the 3-subset {Pikachu, Kirby, Link}: \(P(3, 3) = 3!/(3 - 3)! = 3!\)
- This means that \(P(74, 3)\) overcounts the number of 3-subsets by a ratio of \(3!\) to \(1\).
Combining the general product rule and the k-to-1 rule, we come up with a definition for the number of r-subsets in a set of size \(n\).

n-choose-r

C(n,r): the number of r-subsets from a set of n elements: Let \(r\) and \(n\) be positive integers with \(r \leq n\). The number of r-permutations from a set with \(n\) elements is: \[C(n,r) = \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!}\]

\(C(n,r)\) can also be written \({n \choose r}\) and pronounced “n choose r”

So the number of distinct 3-character teams?

\[S_3 = \dfrac{74!}{3!(74-3)!} = 64,824\]

Counting by complement

There are 225 people and animals in this picture.
How many are not Waldo?

Have you finished counting yet?

Counting by complement

Counting by complement counts the number of elements in a subset \(P \subseteq S\) by counting the elements not in \(P\). \[|P| = |S| - |\overline{P}|\]

Permutations with repetitions

How many ways to scramble Mississippi?

Repeated letters mean that some r-permutations are the same sequence of letters.

\[\text{M}\text{i}_1\text{s}_1\text{s}_2\text{i}_2\text{s}_3\text{s}_4\text{i}_3\text{p}_1\text{p}_2\text{i}_4 = \text{M}\text{i}_2\text{s}_2\text{s}_1\text{i}_1\text{s}_4\text{s}_3\text{i}_4\text{p}_2\text{p}_1\text{i}_3\]

Permutations with repetitions

There are 11 positions to consider, but instead of counting r-permutations, we want to count r-subsets (for r=11).

Let’s break the problem down to choosing positions for each repeated letter.
- For each letter repeated k times, we want to choose k available positions (the order of the repeated letters doesn’t matter since they are identical).
- There are 11 positions for 2 p’s: \(11 \choose 2\)
- That leaves 9 positions for 4 i’s: \(9 \choose 4\)
- That leaves 5 positions for 4 s’s: \(5 \choose 4\)
- That leaves 1 position for 1 M: \(1 \choose 1\)
Now we have 4 sets of choices. Using the product rule to count the total number of choices, we get: \[\begin{align} {11 \choose 2} \cdot {9 \choose 4}\cdot {5 \choose 4}\cdot {1 \choose 1} = \dfrac{11!}{2!9!}\cdot\dfrac{9!}{4!5!}\cdot\dfrac{5!}{4!1!}\cdot\dfrac{1!}{1!} = \dfrac{11!}{2!4!4!1!} \end{align}\]

General formula

For the previous example, we combined the r-subset formula and the product rule.

We can generalize this approach for counting arbitrary permutations on a set \(S\) where \(a_1 \in S\) is repeated \(n_1\) times, \(a_2 \in S\) is repeated \(n_2\), etc.
To find the number of distinct sequences of length \(n\) of elements \(a_i\) from \(S\) where \(a_i\) is repeated \(n_i\) times and \(\sum_i^{n} n_i = n\):

\[{n \choose n_1} \cdot {n - n_1 \choose n_2} \cdot {n - n_1 - n_2 \choose n_3} \cdot {n - n_1 - n_2 ... - n_{k-1} \choose n_k}\] which simplifies to \(\dfrac{n!}{n_1!n_2!...n_k!}\)

Multisets

Multiset: A multiset or bag is a collection that can have multiple instances of the same kind or variety of item.

Like a set, order does not matter. However, the number of each variety of element does matter.

For a set, \(\{b, a, n, a, n, a\} = \{b, a, n\}\). For a multiset, \(\{b, a, n, a, n, a\} \neq \{b, a, n\}\), but \(\{b, a, n, a, n, a\} = \{a, n, a, n, a, b\}\).

What are the varieties of the above multisets?

Assignment problems

Lots of counting problems can be modeled as counting the number of ways to assign elements to numbered bins.
How to count the assignments depends on the distinguishability of the elements and any constraints on the assignments.

Indistinguishable: A collection of identical items are called indistinguishable because it is impossible to distinguish one item from another.
Distinguishable: A collection of different or distinct items are called distinguishable because it is possible to distinguish one item from another.

Balls in bins: no restrictions

On the board:

7 indistinguishable balls, 4 bins
- Assignments are multisets!
7 distinguishable balls, 4 bins
- number the balls
- place each ball in order
- 4 choices each time, so \(4 \cdot 4 \cdot 4 \cdot 4 \cdot 4 \cdot 4 \cdot 4=4^7\)

Balls in bins: \(\leq 1\) per bin

3 indistinguishable balls, 5 bins
- Assignments are 3-subsets!
3 distinguishable balls, 5 bins
- Assignments are 3-permutations!

Balls in bins: same # per bin

10 indistinguishable balls, 5 bins
- Just one way
10 distinguishable balls, 5 bins
- Special case of a 10-permutation on 5 bins with repetition!
- Exactly \(10/5=2\) of each bin number: \({10 \choose 2} \cdot {8 \choose 2} \cdot {6 \choose 2} \cdot {4 \choose 2} \cdot {2 \choose 2}\)

In general: \[{n \choose (n/m)} \cdot {n - (n/m) \choose (n/m)} \cdot {n - 2(n/m) \choose (n/m)} \cdots \cdot {2(n/m) \choose (n/m)} \cdot {(n/m) \choose (n/m)}\] which simplifies to \[\dfrac{n!}{(n/m)!(n/m)!\cdots(n/m)!} = \dfrac{n!}{((n/m)!)^m}\]

“Balls into bins” problems

The number of ways to place \(n\) balls into \(m\) distinguishable bins:

	No restrictions	\(\leq 1\) per bin	same # per bin
\(~\)	\((m \geq 1 \text{ and } n \geq 1)\)	(\(m \geq n\))	(m divides n)
Indistinguishable balls	\[n + m -1 \choose m - 1\]	\[m \choose n\]	\[1\]
Distinguishable balls	\[m^n\]	\[P(m,n)\]	\[\dfrac{n!}{((n/m)!)^m}\]

Silly extra credit

The Burger King I drive by on the way to campus claims there are 221,184 ways to order a Whopper.
- I did a quick calculation using their online menu but got a different number.
For 1% extra credit on your (overall) homework grade,
1. Find a plausible way of counting Whopper configurations that results in 221,184.
2. Propose what the “real” number should be and why, or justify the claimed result.